package NewCoder;

public class BM61 {
    int[][] dirs=new int[][]{{-1,0},{1,0},{0,-1},{0,1}};
    public int solve (int[][] matrix) {
        // write code here
        int m=matrix.length;
        int n=matrix[0].length;
        int res=0;
        int[][] dp=new int[m+1][n+1];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                res=Math.max(res,dfs(matrix,dp,i,j));
            }
        }
        return res;
    }
    private int dfs(int[][] matrix,int[][] dp,int i,int j){
        if(dp[i][j]!=0) return dp[i][j];
        dp[i][j]++;
        for(int k=0;k<4;k++){
            int nexti=i+dirs[k][0];
            int nextj=j+dirs[k][1];
            if(nexti>=0 && nexti<matrix.length && nextj>=0 && nextj<matrix[0].length
                    && matrix[nexti][nextj]>matrix[i][j]){
                dp[i][j]=Math.max(dp[i][j],dfs(matrix,dp,nexti,nextj)+1);
            }
        }
        return dp[i][j];
    }
}
